import collections
class Solution(object):
    def smallestMissingValueSubtree(self, parents, nums):
        n = len(parents)
        t = [-1] * (n + 1)
        d = collections.defaultdict(set)
        for i in range(1, n):
            d[parents[i]].add(i)
        ans = [0] * n
        p = [i for i in range(n)]
        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]
        
        def union(x, y):
            p[y] = x
        
        def dfs(node):
            next_index = 0
            if d[node]:
                next_index = n
                for v in d[node]:
                    next_index = min(dfs(v), next_index)
                    union(node, v)
            t[nums[node] - 1] = node
            while t[next_index] >= 0 and find(t[next_index]) == node:
                next_index += 1
            ans[node] = next_index + 1
            return next_index
        dfs(0)
        return ans




data = Solution()
parents = [-1,0,0,2]
nums = [1,2,3,4]
print(data.smallestMissingValueSubtree(parents, nums))
parents = [-1,0,1,0,3,3]
nums = [5,4,6,2,1,3]
print(data.smallestMissingValueSubtree(parents, nums))